package org.example.ch04;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/permutations/
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
 */
public class Permute {

    public static void main(String[] args) {
        Permute p = new Permute();
        int[] array = new int[]{1,2,3,4};
        List<List<Integer>> list= p.permute(array);


        for (int i = 0; i < list.size(); i++) {
            for (Integer num:list.get(i)){
                System.out.print(num+" ");
            }
            System.out.println();
        }




    }

    /**
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
     * @param nums 1,2,3
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {

        int len = nums.length;
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        //输出内容
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }
        //回溯算法1
//        dfs(nums.length,output,0,res);

        int depth = 0;
        boolean[] used = new boolean[len];
        Deque<Integer> path = new ArrayDeque<Integer>();
        solution1(nums,len,path,res,depth,used);


        return res;
    }

    /**
     * 深度优先遍历
     * @param nums 数组
     * @param len 数组长度
     * @param path  堆栈的路径
     * @param res   返回的集合
     * @param depth  树的深度
     */
    private void solution1(int[] nums, int len, Deque<Integer> path, List<List<Integer>> res, int depth,boolean[] used) {

        //递归的终止条件
        if(depth == len){
            res.add(new ArrayList<>(path));
            return;
        }
        //执行本层逻辑
        for (int i = 0; i < len; i++) {
            if(used[i]){
                //如果已经使用过，则跳过
                continue;
            }
            path.addLast(nums[i]);
            used[i]=true;
            //下探到下一次递归，传入主角
            solution1(nums,len,path,res,depth+1,used);
            //回溯
            path.removeLast();
            used[i]=false;
        }
    }


    /**
     * 回溯算法
     * @param len
     * @param list 1,2,3
     * @param first
     * @param res
     */
    private void dfs(int len,List<Integer> list,int first,List<List<Integer>> res){
        //递归的终结条件
        if(len == first){
            res.add(new ArrayList<>(list));
        }
        //执行本次逻辑
        for (int i = first; i < len; i++) {
            //动态维护数组
            Collections.swap(list,first,i);
            //下探到下一层，传入主角
            dfs(len,list,first+1,res);
            //清理本层,撤销操作
            Collections.swap(list,first,i);
        }
    }



}
